训练指南 UVA - 11354（最小生成树 + 倍增LCA）

Diposting di | Edited on

Bond

UVA - 11354

题意

给你一张无向图，然后有若干组询问，让你输出a->b的最小瓶颈路

题解

先求出最小生成树,然后对这个最小生成树做LCA。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+50;
const int logmaxn=20;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct LCA{
    int n;
    int fa[maxn];       ///父亲数组
    int cost[maxn];     ///和父亲的费用
    int L[maxn];        ///层次(根节点为0)
    int anc[maxn][logmaxn];     /// anc[p][i]是结点p的第2^i级父亲。anc[i][0] = fa[i]
    int maxcost[maxn][logmaxn]; /// maxcost[p][i]是i和anc[p][i]的路径上的最大费用
    void preprocess(){
        for(int i=0;i<n;i++){
            anc[i][0]=fa[i];maxcost[i][0]=cost[i];
            for(int j=1;(1<<j)<n;j++)anc[i][j]=-1;
        }
        for(int j=1;(1<<j)<n;j++)
            for(int i=0;i<n;i++)
        if(anc[i][j-1]!=-1){
            int a=anc[i][j-1];
            anc[i][j]=anc[a][j-1];
            maxcost[i][j]=max(maxcost[i][j-1],maxcost[a][j-1]);
        }
    }
    /// 求p到q的路径上的最大权
    int query(int p,int q){
        int tmp,log,i;
        if(L[p]<L[q])swap(p,q);
        for(log=1;(1<<log)<=L[p];log++);log--;
        int ans=-inf;
        for(int i=log;i>=0;i--)
        if(L[p]-(1<<i)>=L[q]){ans=max(ans,maxcost[p][i]);p=anc[p][i];}

        if(p==q)return ans; ///LCA为p

        for(int i=log;i>=0;i--)
        if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
            ans=max(ans,maxcost[p][i]);p=anc[p][i];
            ans=max(ans,maxcost[q][i]);q=anc[q][i];
        }
        ans=max(ans,cost[p]);
        ans=max(ans,cost[q]);
        return ans; ///LCA为fa[p]（它也等于fa[q]）
    }
};
LCA solver;
int pa[maxn];
int findset(int x){return pa[x]!=x?pa[x]=findset(pa[x]):x;}
vector<int>G[maxn],C[maxn];
void dfs(int u,int fa,int level){
    solver.L[u]=level;
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(v!=fa){
            solver.fa[v]=u;
            solver.cost[v]=C[u][i];
            dfs(v,u,level+1);
        }
    }
}

struct Edge{
    int x,y,d;
    bool operator <(const Edge& rhs)const{
        return d<rhs.d;
    }
};
const int maxm=1e5+10;
Edge e[maxm];

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int kase=0,n,m,x,y,d,Q;
    while(cin>>n>>m){
        for(int i=0;i<m;i++){
            cin>>x>>y>>d;e[i]=(Edge){x-1,y-1,d};
        }
        sort(e,e+m);
        for(int i=0;i<n;i++){pa[i]=i;G[i].clear();C[i].clear();}
        for(int i=0;i<m;i++){
            int x=e[i].x,y=e[i].y,d=e[i].d,u=findset(x),v=findset(y);
            if(u!=v){
                pa[u]=v;
                G[x].push_back(y);G[y].push_back(x);
                C[x].push_back(d);C[y].push_back(d);
            }
        }
        solver.n=n;
        dfs(0,-1,0);
        solver.preprocess();
        if(++kase!=1)cout<<endl;
        cin>>Q;
        while(Q--){
            cin>>x>>y;
            cout<<solver.query(x-1,y-1)<<endl;
        }
    }
    return 0;
}